package lc;
import java.util.*;
import org.junit.*;
public class Ex227 {
    class Solution {
        public int calculate(String s) {
            s = s.replace(" ", "");
            char[] cs = s.toCharArray();
            Stack<Integer> nums = new Stack<>();
            Stack<Character> calcs = new Stack<>();
            int last = 0, len = cs.length, j;
            char c;
            Map<Character, Integer> map = new HashMap<>();
            map.put('+', 1);
            map.put('-', 1);
            map.put('*', 2);
            map.put('/', 2);
    
            for (int i = 0; i < len; i++) {
                c = cs[i];
                if (isDigit(c)) {
                    j = i;
                    last = 0;
                    while (j < len && isDigit(cs[j])) {
                        last = last * 10 + cs[j++] - '0';
                    } 
                    i = j - 1;
                    nums.push(last);
                } else {
                    if (calcs.isEmpty() || map.get(c) > map.get(calcs.peek())) {
                        calcs.push(c);
                    } else {
                        while (!calcs.isEmpty() && map.get(c) <= map.get(calcs.peek())) {
                            int b = nums.pop(), a = nums.pop();
                            char t = calcs.pop();
                            nums.push(calc(a, b, t));
                        }
                        calcs.push(c);
                    }
                }
            }
    
            while (!calcs.isEmpty()) {
                int b = nums.pop(), a = nums.pop();
                char t = calcs.pop();
                nums.push(calc(a, b, t));
            }
            return nums.peek();
        }
    
        public boolean isDigit(char c) {
            return c >= '0' && c <= '9';
        }
    
        public int calc(int a, int b, char c) {
            switch(c) {
                case '+':
                    return a + b;
                case '-':
                    return a - b;
                case '*':
                    return a * b;
                case '/':
                    return a / b;                
            }
            return -1;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.calculate("3+2*2"));        
    }
}
